#include "shell_sort.h"

void swap(int * a,int * b){
	int temp=*a;
	*a=*b;
	*b=temp;
}

int median(int array[],int left,int right){
	int center=(left+right)/2;
	if(array[left]>array[center])
		swap(&array[left],&array[center]);
	if(array[left]>array[right])
		swap(&array[left],&array[right]);
	if(array[center]>array[right])
		swap(&array[center],&array[right]);
	swap(&array[center],&array[right-1]);
	return array[right-1];
}

void fastsort(int array[],int left,int right){
	int pivot,low,high;
	int cutoff=100;
	if(cutoff<=right-left){
		pivot=median(array,left,right);
		low=left;
		high=right-1;
		while(1){
			while(array[++low]<pivot);
			while(array[--high]>pivot);
			if(low<high){
				swap(&array[low],&array[high]);
			}else{
				break;
			}
		}
		swap(&array[low],&array[right-1]);
		fastsort(array,left,low-1);
		fastsort(array,low+1,right);
	}else{
		ShellSort(array+left,right-left+1);
	}
}

void QuickSort(int array[],int n){
	fastsort(array,0,n-1);
}
